A router implementing an Exterior Gateway Protocol (EGP) such as Border Gateway Protocol (BGP), typically generates update messages that are sent to its peers, in order to propagate routing information to the peers. Peers who share a same outbound policy may be grouped together into peer groups (update groups). An update group reduces the load on system resources by allowing the router to generate a common set of update messages, which are replicated to all update group members. This can significantly reduce the resources consumed in comparison to treating each peer in the update group individually. However, sometimes one or more peers in an update group persistently cannot keep up with the flow of update messages. When a peer in an update group cannot keep up, the number of update messages pending transmission may build up, and the update group is “throttled” back. The rest of the members of the update group, which can keep up, are forced to wait for the peer to consume update messages. Even if new routing information is available for the rest of the members of the update group, the presence of the peer that cannot keep up in the update group effectively blocks generation of new update messages for the other peers. Accordingly, there is a need for improved techniques for identifying and dealing with peers in an update group that persistently cannot keep up with the flow of update messages.